package leetcode_500;

import java.util.ArrayList;
import java.util.List;

/**
 *@author 周杨
 *FindAllNumbersDisappearedInAnArray_448 给定一个特殊数组 里面存放特殊元素 1 ≤ a[i] ≤ n (n = size of array) 找出没有出现过的元素 
 *describe:用标记位 出现的置负数 AC 16%
 *2018年8月22日 上午10:31:42
 */
public class FindAllNumbersDisappearedInAnArray_448 {
	public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res=new ArrayList<Integer>();
        if(nums.length==0)
        	return res;
        for(int num:nums) {
        	int now=Math.abs(num);
        	if(nums[now-1]>0)
        		nums[now-1]=-nums[now-1];
        }
        for(int i=0;i<nums.length;++i) {
        	if(nums[i]>0)
        		res.add(i);
        }
        return res;
    }
}
